﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq.Expressions;
using Library.Collections.Generic;
using Library.Linq;
using INDEX = System.UInt64;

namespace Library.Collections.Specialized
{
    [DebuggerDisplay("Count={Count}")]
    public sealed class PriorityQueueDescending<T, TKey> : IQueue<T>, IOrderedEnumerable<T>
    {
        public PriorityQueueDescending(Func<T, TKey> keySelector)
        {
            this.data = new T[0];
            this.count = 0;
            this.version = 0;
            this.keySelector = keySelector;
            this.comparer = null;
        }
        public PriorityQueueDescending(Func<T, TKey> keySelector, IComparer<TKey> comparer)
        {
            this.data = new T[0];
            this.count = 0;
            this.version = 0;
            this.keySelector = keySelector;
            this.comparer = comparer;
        }

        T[] data;
        INDEX count;
        INDEX version;
        Func<T, TKey> keySelector;
        IComparer<TKey> comparer;

        public bool Enqueue(T item)
        {
            version++;
            if (count >= (INDEX)data.Length)
                Array.Resize(ref data, (int)Math.Max(Math.Max((INDEX)data.Length * 2, 4), count + 1));
            ++count;
            if (count == 1)
                data[0] = item;
            else
                SiftUp(count - 1, item);
            return true;
        }

        public bool Dequeue(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            INDEX s = --count;
            version++;
            item = data[0];
            T x = data[s];
            data[s] = default(T);
            if (s != 0)
                SiftDown(0, x);
            return true;
        }

        public bool Peek(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[0];
            return true;
        }

        public bool Contains(T item)
        {
            return Array.IndexOf(data, item, 0, (int)count) >= 0;
        }

        public INDEX Count
        {
            get { return count; }
        }

        private void SiftUp(INDEX n, T item)
        {
            TKey item_key = keySelector(item);
            if (comparer == null)
            {
                IComparable<TKey> item_key_comparable = (IComparable<TKey>)item_key;
                while (n > 0)
                {
                    INDEX parent = (n - 1) >> 1;
                    T t = data[parent];
                    if (item_key_comparable.CompareTo(keySelector(t)) < 0)
                        break;
                    data[n] = t;
                    n = parent;
                }
                data[n] = item;
            }
            else
            {
                while (n > 0)
                {
                    INDEX parent = (n - 1) >> 1;
                    T t = data[parent];
                    if (comparer.Compare(item_key, keySelector(t)) < 0)
                        break;
                    data[n] = t;
                    n = parent;
                }
                data[n] = item;
            }
        }

        private void SiftDown(INDEX n, T item)
        {
            TKey item_key = keySelector(item);
            INDEX half = count >> 1;
            if (comparer == null)
            {
                IComparable<TKey> item_key_comparable = (IComparable<TKey>)item_key;
                while (n < half)
                {
                    INDEX child = (n << 1) + 1;
                    T c = data[child];
                    TKey c_key = keySelector(c);
                    INDEX right = child + 1;
                    if (right < count && ((IComparable<TKey>)c_key).CompareTo(keySelector(data[right])) <= 0)
                        c = data[child = right];
                    if (item_key_comparable.CompareTo(c_key) > 0)
                        break;
                    data[n] = c;
                    n = child;
                }
                data[n] = item;
            }
            else
            {
                while (n < half)
                {
                    INDEX child = (n << 1) + 1;
                    T c = data[child];
                    TKey c_key = keySelector(c);
                    INDEX right = child + 1;
                    if (right < count && comparer.Compare(c_key, keySelector(data[right])) <= 0)
                        c = data[child = right];
                    if (comparer.Compare(item_key, c_key) > 0)
                        break;
                    data[n] = c;
                    n = child;
                }
                data[n] = item;
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }

        System.Collections.IEnumerable IOrderedEnumerable.Input
        {
            get { return null; }
        }

        LambdaExpression IOrderedEnumerable.Comparison
        {
            get { throw new NotImplementedException(); }
        }

        LambdaExpression IOrderedEnumerable.KeySelector
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        System.Collections.IComparer IOrderedEnumerable.Comparer
        {
            get
            {
                if (comparer == null) return null;
                System.Collections.IComparer _comparer = comparer as System.Collections.IComparer;
                if (_comparer != null)
                    return _comparer;
                return new Library.Collections.Specialized.Comparer<TKey>(comparer);
            }
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }
    }

    [DebuggerDisplay("Count={Count}")]
    public sealed class PriorityQueueCachingDescending<T, TKey> : IQueue<T>, IOrderedEnumerable<T>
    {
        public PriorityQueueCachingDescending(Func<T, TKey> keySelector)
        {
            this.data = new MutableTuple<T, TKey>[0];
            this.count = 0;
            this.version = 0;
            this.keySelector = keySelector;
            this.comparer = null;
        }
        public PriorityQueueCachingDescending(Func<T, TKey> keySelector, IComparer<TKey> comparer)
        {
            this.data = new MutableTuple<T, TKey>[0];
            this.count = 0;
            this.version = 0;
            this.keySelector = keySelector;
            this.comparer = comparer;
        }

        MutableTuple<T, TKey>[] data;
        // also possible T[] data1; TKey[] data2;
        INDEX count;
        INDEX version;
        Func<T, TKey> keySelector;
        IComparer<TKey> comparer;

        public bool Enqueue(T item)
        {
            version++;
            if (count >= (INDEX)data.Length)
                Array.Resize(ref data, (int)Math.Max(Math.Max((INDEX)data.Length * 2, 4), count + 1));
            ++count;
            if (count == 1)
            {
                data[0].Item1 = item;
                data[0].Item2 = keySelector(item);
            }
            else
                SiftUp(count - 1, item, keySelector(item));
            return true;
        }

        public bool Dequeue(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            INDEX s = --count;
            version++;
            item = data[0].Item1;
            T x = data[s].Item1;
            TKey x_key = data[s].Item2;
            data[s].Item1 = default(T);
            data[s].Item2 = default(TKey);
            if (s != 0)
                SiftDown(0, x, x_key);
            return true;
        }

        public bool Dequeue(out T item, out TKey key)
        {
            if (count == 0)
            {
                item = default(T);
                key = default(TKey);
                return false;
            }
            INDEX s = --count;
            version++;
            item = data[0].Item1;
            key = data[0].Item2;
            T x = data[s].Item1;
            TKey x_key = data[s].Item2;
            data[s].Item1 = default(T);
            data[s].Item2 = default(TKey);
            if (s != 0)
                SiftDown(0, x, x_key);
            return true;
        }

        public bool Peek(out T item)
        {
            if (count == 0)
            {
                item = default(T);
                return false;
            }
            item = data[0].Item1;
            return true;
        }

        public bool Peek(out T item, out TKey key)
        {
            if (count == 0)
            {
                item = default(T);
                key = default(TKey);
                return false;
            }
            item = data[0].Item1;
            key = data[0].Item2;
            return true;
        }

        public bool Contains(T item)
        {
            for (INDEX index = 0; index < count; ++index)
            {
                T current = data[index].Item1;
                if (current.Equals(item))
                    return true;
            }
            return false;
        }

        public INDEX Count
        {
            get { return count; }
        }

        private void SiftUp(INDEX n, T item, TKey item_key)
        {
            if (comparer == null)
            {
                IComparable<TKey> item_key_comparable = (IComparable<TKey>)item_key;
                while (n > 0)
                {
                    INDEX parent = (n - 1) >> 1;
                    T t = data[parent].Item1;
                    TKey t_key = data[parent].Item2;
                    if (item_key_comparable.CompareTo(t_key) < 0)
                        break;
                    data[n].Item1 = t;
                    data[n].Item2 = t_key;
                    n = parent;
                }
                data[n].Item1 = item;
                data[n].Item2 = item_key;
            }
            else
            {
                while (n > 0)
                {
                    INDEX parent = (n - 1) >> 1;
                    T t = data[parent].Item1;
                    TKey t_key = data[parent].Item2;
                    if (comparer.Compare(item_key, keySelector(t)) < 0)
                        break;
                    data[n].Item1 = t;
                    data[n].Item2 = t_key;
                    n = parent;
                }
                data[n].Item1 = item;
                data[n].Item2 = item_key;
            }
        }

        private void SiftDown(INDEX n, T item, TKey item_key)
        {
            INDEX half = count >> 1;
            if (comparer == null)
            {
                IComparable<TKey> item_key_comparable = (IComparable<TKey>)item_key;
                while (n < half)
                {
                    INDEX child = (n << 1) + 1;
                    T c = data[child].Item1;
                    TKey c_key = data[child].Item2;
                    INDEX right = child + 1;
                    if (right < count && ((IComparable<TKey>)c_key).CompareTo(data[right].Item2) <= 0)
                    {
                        c = data[child = right].Item1;
                        c_key = data[child].Item2;
                    }
                    if (item_key_comparable.CompareTo(c_key) > 0)
                        break;
                    data[n].Item1 = c;
                    data[n].Item2 = c_key;
                    n = child;
                }
                data[n].Item1 = item;
                data[n].Item2 = item_key;
            }
            else
            {
                while (n < half)
                {
                    INDEX child = (n << 1) + 1;
                    T c = data[child].Item1;
                    TKey c_key = data[child].Item2;
                    INDEX right = child + 1;
                    if (right < count && comparer.Compare(c_key, data[right].Item2) <= 0)
                    {
                        c = data[child = right].Item1;
                        c_key = data[child].Item2;
                    }
                    if (comparer.Compare(item_key, c_key) > 0)
                        break;
                    data[n].Item1 = c;
                    data[n].Item2 = c_key;
                    n = child;
                }
                data[n].Item1 = item;
                data[n].Item2 = item_key;
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }

        System.Collections.IEnumerable IOrderedEnumerable.Input
        {
            get { return null; }
        }

        LambdaExpression IOrderedEnumerable.Comparison
        {
            get { throw new NotImplementedException(); }
        }

        LambdaExpression IOrderedEnumerable.KeySelector
        {
            get
            {
                throw new NotImplementedException();
            }
        }

        System.Collections.IComparer IOrderedEnumerable.Comparer
        {
            get
            {
                if (comparer == null) return null;
                System.Collections.IComparer _comparer = comparer as System.Collections.IComparer;
                if (_comparer != null)
                    return _comparer;
                return new Library.Collections.Specialized.Comparer<TKey>(comparer);
            }
        }

        public bool IsReadOnly
        {
            get
            {
                return false;
            }
        }
    }
}
